package leetcode.newcoder;

import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by tiang on 2018/7/26.
 * 题目描述
     牛牛和 15 个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，
     每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16 份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地，
     作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？
 输入描述:
    每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 75），
    表示田地的大小，接下来的 n 行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。
 输出描述:
    输出一行表示牛牛所能取得的最大的价值。
 输入
         4 4
         3332
         3233
         3332
         2323
 输出
        2
 */
public class DivideArea {

    /**
     * 这种做法的思想就是找到每次最小的那块区域，然后对其进行扩张，有两种扩张方式，行扩张或者列扩张
     * 重新寻找扩张之后的最小区域，然后再对其进行扩张
     * 直到扩张到边界
     * 这种算法会超时，时间复杂度为2^n
     */

    /**
     * 标注唯一分法
     * @param rows
     * @param cols
     * @return
     */
    private static String getKey(int[] rows, int[] cols) {
        String r = "", c = "";
        for (int i = 0; i < rows.length; i++) {
            r += rows[i];
            c += cols[i];
        }
        return r + c;
    }

    /**
     * 返回这块区域在指定分法下最小区域的面积
     * @param area 区域
     * @param rows 行分法
     * @param cols 列分法
     * @param pres 以前处理过的分法的中间结果
     * @param sum 记录以某个点为右下角，0,0 为左上角构成的矩形的面积
     * @return 最小区域的面积
     */
    private static int getMaxValue(int[][] area, int[] rows, int[] cols, HashMap<String, Integer> pres, int[][] sum) {
        // 获取这种分法的标识
        String key = getKey(rows, cols);
        // 以前是否分过，如果分过就直接返回
        if(pres.containsKey(key)) {
            return pres.get(key);
        }
        // 获取面积最小的那块地
        Node least = getLeastArea(rows, cols, sum);
        int result = 0;
        // 如果还没有扩张到边界
        if (rows[3] == area.length && cols[3] == area[0].length)
            result = least.value;
        else {
            // 行扩张
            if (rows[3] < area.length) {
                // 扩张后的行分法
                int[] expandRow = expand(rows, least.x);
                // 行扩张后的最小区域面积
                int rowMax = getMaxValue(area, expandRow, cols, pres, sum);
                result = Math.max(result, rowMax);
            }
            // 列扩张
            if (cols[3] < area[0].length) {
                // 扩张后的列分法
                int[] expandCol = expand(cols, least.y);
                // 列扩张之后的最小区域面积
                int colMax = getMaxValue(area, rows, expandCol, pres, sum);
                result = Math.max(result, colMax);
            }
        }
        // 将该分法的结果记录下来
        pres.put(key, result);
        return result;
    }

    /**
     * 扩充该田地
     * @param nums 原来的行分法或者列分法
     * @param k 从指定位置开始向外扩张
     */
    private static int[] expand(int[] nums, int k){
        int[] newNums = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            if(i>=k)
                newNums[i] = nums[i]+1;
            else
                newNums[i] = nums[i];
        }
        return newNums;
    }

    /**
     * 存放分割后的田地块坐标及其面积
     */
    static class Node{
        // 存放该田地的右下角坐标，以及该田地的面积
        public int x, y, value;
        public Node(int x, int y, int v){
            this.x = x;
            this.y = y;
            this.value = v;
        }
    }

    /**
     * 寻找整个分法过程中最小的那一块地
     * @param rows
     * @param cols
     * @return
     */
    private static Node getLeastArea(int[] rows, int[] cols, int[][] sum){
        Node least = new Node(-1, -1, Integer.MAX_VALUE);
        for(int i=0;i<rows.length;i++){
            for(int j=0;j<cols.length;j++){
                int value = calculateArea(sum, i==0?0:rows[i-1], rows[i], j==0?0:cols[j-1], cols[j]);
                if(value<least.value)
                    least = new Node(i, j, value);
            }
        }

        return least;
    }

    /**
     * 计算指定区域的面积和
     * @param sum 面积集合
     * @param rowStart 起始行
     * @param rowEnd 结束行
     * @param colStart 起始列
     * @param colEnd 结束列
     * @return 区域面积
     */
    private static int calculateArea(int[][] sum, int rowStart, int rowEnd, int colStart, int colEnd) {
        int temp = sum[rowEnd][colEnd] - sum[rowEnd][colStart] - sum[rowStart][colEnd] + sum[rowStart][colStart];
        return temp;
    }
    public static void main(String[] args) {
        int[] rows = new int[]{
                1, 2, 3, 4
        },
                cols = new int[]{
                        1, 2, 3, 4
                };
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),
                m = scanner.nextInt();
        int[][] map = new int[n][m];
        scanner.nextLine();
        for(int i=0;i<n;i++){
            char[] nums = scanner.nextLine().toCharArray();
            for(int j=0;j<m;j++){
                map[i][j] = nums[j] - '0';
            }
        }
        // 计算以当前格子为右下角，原点为左上角形成的矩形区域的面积
        int[][] sum = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
            {
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + map[i-1][j-1];
            }
        }
        HashMap<String, Integer> temp = new HashMap<>();
        long before = System.currentTimeMillis();
        int result = getMaxValue(map, rows, cols, temp, sum);
        long after = System.currentTimeMillis();
        System.out.println(result);
        System.out.println("waste time: "+(after-before));

        before = System.currentTimeMillis();
        System.out.println(getMaxMinArea(sum, n, m));
        after = System.currentTimeMillis();
        System.out.println("second time: "+(after-before));
    }

    private static int getMaxMinArea(int[][] sum, int n, int m){
        int max = sum[n][m],
                min = 1;
        while(max > min){
            int middle = (max+min)/2;
            if(isAlright(sum, n, m, middle))
                min = middle+1;
            else
                max = middle-1;
        }
        return isAlright(sum, n, m, max)? max:max-1;
    }

    private static boolean isAlright(int[][] sum, int n, int m, int aim) {

        for (int j = 1; j < m - 2; j++) {
            for (int k = j + 1; k < m - 1; k++) {
                for (int t = k + 1; t < m; t++) {
                    int lastRow = 0;
                    int rightRowCount = 0;
                    for (int i = 1; i <= n; i++) {
                        int a1 = calculateArea(sum, lastRow, i, 0, j);
                        int a2 = calculateArea(sum, lastRow, i, j, k);
                        int a3 = calculateArea(sum, lastRow, i, k, t);
                        int a4 = calculateArea(sum, lastRow, i, t, m);
                        int count = 0;
                        if (a1 >= aim)
                            count++;
                        if (a2 >= aim)
                            count++;
                        if (a3 >= aim)
                            count++;
                        if (a4 >= aim)
                            count++;
                        if (count == 4) {
                            lastRow = i;
                            rightRowCount++;
                            if (rightRowCount >= 4)
                                return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}
